A network may include a plurality of interconnected systems or nodes, and may comprise, for example, without limitation, computers, set top boxes, peripherals, servers and/or terminals coupled by communications lines or other communications channels. A network may connect or couple systems over a local area (e.g., a campus) or over a wide area (e.g., multiple campuses).
High-speed packet-switching networks, such as Asynchronous Transfer Mode (ATM), Internet Protocol (IP), and Gigabit Ethernet, support a multitude of connections to different sessions. Typically, packet-switching systems are employed to transmit blocks of data, called packets. The packets may have fixed size or they may have variable sizes. Each packet may include control information in a header. The control information may include routing information to route the packet through the network to a destination, and information to indicate a start of a packet and an end of the packet. The control information may also include information to indicate whether a packet is a last packet (or tail packet).
Many systems (e.g., framers, network processors, etc.) implement packet-based interfaces. For example, the interface may be the ATM Forum's Universal Test & Operations Physical Interface for ATM (UTOPIA) or Optical Internetworking Forum (OIF)'s System Packet Interface (SPI-3 and SPI-4). FIG. 1A is a block diagram illustrating an example of an interface. The interface 110 may be, for example, an UTOPIA interface. The interface 110 may also be, for example, an SPI interface. ATM data may be exchanged between the physical layer 105 and the ATM layer 115 through the interface 110. The interface 110 may include components to interface with the physical layer 105 and components to interface with the ATM layer 115. These components may include FIFO (first-in first-out) controllers that handle reading from and writing to FIFO buffers in a memory. There may be multiple physical devices in the physical layer 105, and there may be multiple ATM devices in the ATM layer 115. There may be one FIFO controller for each of the physical and ATM devices. The interface 110 may also include other components. The-FIFO controller is typically implemented across two clock domains—a clock domain for the interface and a clock domain for the corresponding device.
FIG. 1B is a block diagram illustrating an example of a prior art partitioning of a physical memory. Typically, memory 100 is divided into equal fixed-size partitions with each of the partitions used as a FIFO buffer and assigned to a logical port. Each logical port may be associated with a device (e.g., ATM device). For example, the size of the memory 100 may be 16 Kbytes, and the memory 100 may be divided into 64 partitions. Each of the 64 partitions may be statically assigned to a logical port (e.g., the partition 1 is assigned to the logical port 1, etc.) such that every logical port is associated with at most one partition. There is no free partition. In this example, each partition is 256 bytes long. This partitioning technique is referred to as complete partitioning (CP). When using CP, memory space in a partition may be wasted if the associated assigned logical port is inactive. The wasted memory space cannot be used by another active logical port. Thus, while one active logical port may experience packet overflow, there may be one or more inactive logical ports that may not fully utilize their FIFO buffers.
In another prior art, an arriving packet is accepted into the memory if there is any available memory space regardless of how much memory space the associated logical port is utilizing. For example, there may be multiple FIFO buffers each having different sizes. When there is no available memory space, an arriving packet is dropped. When a logical port is utilizing memory space and the data stored in the memory space is not read, that logical port may monopolize the memory space it is utilizing leaving little left for the other logical ports. This technique is referred to as complete sharing (CS). When using CS, a heavily utilized logical port punishes a lightly utilized logical port.
The allocation of memory space to FIFO buffers is made worse by the emerging standards ANSI T1.105-2001 (Synchronous Optical Network (SONET)) that describes virtual bandwidth allocation and allows each logical port to transfer at a dynamically changing rate.